package 树;

import 抽象数据类型.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import static 抽象数据类型.TreeNode.buildTree;

/**
 * @description:
 * @author: ywk
 * @date: 2020-12-17
 */
public class 求二叉树中最大路径和 {
    static int ans = Integer.MIN_VALUE;
    static int maxVal = 0;


    private static int oneSideMax(TreeNode<Integer> root) {
        if (root == null) return 0;
        int left = Math.max(0, oneSideMax(root.left));
        int right = Math.max(0, oneSideMax(root.right));
        ans = Math.max(ans, left + right + root.val);
        return Math.max(left, right) + root.val;
    }
    private static int dfs(TreeNode<Integer> root) {
        List<Integer> list = new ArrayList<>();
        if (root.left != null) {
            list.add(dfs(root.left) + root.left.val);
        }
        if (root.right != null) {
            list.add(dfs(root.right) + root.right.val);
        }
        Collections.sort(list);
        int n = list.size(), val = 0;
        for (int i = n - 1; i >= 0 && i >= n - 2; --i) {
            val += list.get(i);
        }
        maxVal = Math.max(maxVal, val);
        return n == 0 ? 0 : list.get(n - 1);
    }
    public static void main(String[] args) {
        Integer[] str = new Integer[]{3, -1, 3, null, null, 1, 2};
        TreeNode treeNode = buildTree(new ArrayList<>(Arrays.asList(str)));
        System.out.println(oneSideMax(treeNode));
        System.out.println(dfs(treeNode));
    }
}
